package com.maokeyang.linkedlist.question;


import java.util.Arrays;
import java.util.List;

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }

    @Override
    public String toString() {
        return String.valueOf(val);
    }
}

/**
 * 链表操作
 */
public class Solution {

    /**
     * 根据List生成对应 的链表
     *
     * @param dataList
     * @return ListNode
     */
    public ListNode initLinkList(List<Integer> dataList) {

        if (dataList.size() == 0) {
            return null;
        }

        ListNode listNode = new ListNode(dataList.get(0));
        listNode.next = initLinkList(dataList.subList(1, dataList.size()));
        return listNode;
    }


    /**
     * 生成 1 - N 的链表
     *
     * @param num
     * @return ListNode
     */
    public ListNode createLinkList(int num) {
        return createLinkList(num, 1);
    }

    private ListNode createLinkList(int num, int k) {
        if (k > num) {
            return null;
        }

        ListNode listNode = new ListNode(k);
        listNode.next = createLinkList(num, ++k);
        return listNode;
    }

    /**
     * 链表打印
     * @param l
     * @return
     */
    public void printLinkList(ListNode l) {
        StringBuilder res = new StringBuilder();

        res.append("链表打印：");
        while (l != null) {
            res.append(l + "-->");
            l = l.next;
        }

        res.append("NULL");

        System.out.println(res.toString());
    }


    /**
     * 206 反转一个单链表
     *
     * 输入: 1->2->3->4->5->NULL
     * 输出: 5->4->3->2->1->NULL
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
       if (head == null || head.next == null) {
           return head;
       }

       ListNode tmp = reverseList(head.next);
       head.next.next = head;
       head.next = null;

       return tmp;
    }

    /**
     * 206 反转一个单链表2
     *
     * 输入: 1->2->3->4->5->NULL
     * 输出: 5->4->3->2->1->NULL
     * @param head
     * @return
     */
    public ListNode reverseList2(ListNode head) {
        ListNode prev = null;

        while (head != null) {
            ListNode tmp = head.next;
            head.next = prev;
            prev = head;
            head = tmp;
        }
        return prev;
    }


    /**
     * 2. 两数相加
     * 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
     *
     * 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
     *
     * 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
     *
     *
     * 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
     * 输出：7 -> 0 -> 8
     * 原因：342 + 465 = 807
     *
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return null;
    }

    /**
     * 24. 两两交换链表中的节点
     *
     * 给定 1->2->3->4, 你应该返回 2->1->4->3.
     *
     * @param head
     * @return null
     */
    public ListNode swapPairs(ListNode head) {
        return null;
    }


    /**
     * 21. 合并两个有序链表
     *
     * 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
     *
     * 输入：1->2->4, 1->3->4
     * 输出：1->1->2->3->4->4
     *
     * @param l1
     * @param l2
     * @return
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return l1 == null ? l2 : l1;
        }

        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }


    /**
     * 83. 删除排序链表中的重复元素
     * 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
     *
     * 输入: 1->1->2
     * 输出: 1->2
     *
     * 输入: 1->1->2->3->3
     * 输出: 1->2->3
     *
     * @param head
     */
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;

        while (head.next != null) {
            if (head.val == head.next.val) {
                head.next = head.next.next;
            }
            head = head.next;
        }

        return dummyNode.next;
    }

    /**
     * 测试的Main方法
     * 
     * @param args
     */
    public static void main(String[] args) {
        Solution solution = new Solution();

        //ListNode listNode = solution.createLinkList(9);

        ListNode l1 = solution.initLinkList(Arrays.asList(1, 2, 4));
        solution.printLinkList(l1);

        ListNode l2 = solution.initLinkList(Arrays.asList(1, 3, 4));
        solution.printLinkList(l2);

        ListNode listNode = solution.mergeTwoLists(l1, l2);

        solution.printLinkList(listNode);

    }
}
